package problem692;

import java.util.*;

//692.前k个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>((a, b)->{
            if(a.getValue() != b.getValue()) return a.getValue()-b.getValue();
            else return b.getKey().compareTo(a.getKey());
        });
        for(String s : words) {
            if(!map.containsKey(s)) map.put(s, 1);
            else map.put(s, map.get(s) + 1);
        }

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            queue.add(entry);
            if(queue.size() > k) queue.poll();
        }

        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()) {
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}